Identification, e.g. optical document scanning, or navigation, e.g. optical detection by an optical mouse, is difficult on highly repetitive surfaces, e.g. a halftone print of an image, where dots of ink are spaced at regular intervals on the printing surface, because the images taken of the surface at displacements that are related to the repetition spacing are virtually identical. This ambiguity in displacements results in significant errors in tracking motion. More precisely, when the repetition rate is high enough to produce one or more periods within the window of displacements searched by a navigation device, occasional false displacements are expected, leading to large tracking errors.
Methods for detecting halftones have been proposed in optical document scanning. One method uses a two-step process involving a Fourier transform of the entire document followed by filtering with a Gabor filter tuned from the results of the Fourier transform as disclosed by Dunn, et al. in “Extracting halftones from printed documents using texture analysis,” Proceedings of the 1996 International Conference on Image Processing, pp. 225–228. Another method, developed for document analysis, also uses two-step processing, starting with a wavelet transform in the first step and detecting halftones with a Fourier transform applied to the wavelet sub-bands as disclosed by Kuo, et al. in “Color halftone document segmentation and screening,” Proceedings of the 2001 International Conference on Image Processing, pp. 1065–1068.
Both methods require a substantial amount of memory, large enough to store a digital scan of an entire document and significant processing power to compute a Fourier transform. These requirements may be appropriate to a desktop personal computer but cannot be met in an inexpensive optical navigation component with limited memory and processing capability.
Because half-toned images are used on many mouse pads and artificial replica wood surfaces, it is important for optical detectors to detect their presence and make navigation decision accordingly to avoid tracking errors.